package com.itheima.kuaipai;

import java.util.Arrays;

public class Test {

    public static void main(String[] args) {
        int[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};

        kuaipai(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));

    }

    // 给基准数 找位置
    //参数  int[] arr   左边的起始索引    右边的结束索引
    //返回值  void
    public static void kuaipai(int[] arr, int left, int right) {
        if (right < left) {
            return;
        }

        int left0 = left;//保留 左边的位置
        int rigth0 = right;
        //1.找到基准数
        int ji = arr[left0];
        //5 循环找 //如果 左边=右边
        while (left != right) {
            //arr[right]  arr[left]  ji
            //2.从右边开始找 比基准数小的  arr[right]<ji 停下来
            while (arr[right] >= ji && left < right) {
                right--;
            }
            //3. 从左边找比 基准数 大的
            while (arr[left] <= ji && left < right) {
                left++;
            }

            //4. 交换
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
        //6.基准数归位  arr[left0]  arr[left]
        //循环结束以后的left 就应该是基准数的位置

        int temp = arr[left0];
        arr[left0] = arr[left];
        arr[left] = temp;

        //6 左边 继续排序  不断的缩小规模

        kuaipai(arr, left0, left - 1);
        //6 右边继续排序
        kuaipai(arr, left + 1, rigth0);

    }


}
